package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/21 16:19
 * @description :5道
 * 见过领军同学（猴，周峰），一个是三年没见，一个是一年没见，还好还好，此行花费约160元，住了一次人生最便宜宾馆（14元），真够难受的。开始准备论文了，开始忙起来了。
 * persevere to last
 * 2021.11.21
 * 李红磊
 * 2021年11月21日20:48:23
 */
public class t20211121 {

    //559.N叉树的最大深度
    public int maxDepth(Node root) {
        if (root == null) return 0;
        if (root.children == null || root.children.size() == 0) return 1;

        ArrayDeque<Node> queue = new ArrayDeque<Node>() {{
            addLast(root);
        }};
        int count = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Node poll = queue.pollFirst();
                if (poll.children.size() == 0 || poll.children == null) continue;
                else {
                    for (Node item : poll.children) queue.addLast(item);
                }
            }
            count++;

        }

        return count;
    }

    //剑指45.把数组排成最小的数
    public String minNumber(int[] nums) {
        if (nums == null || nums.length == 0) return "";


        int len = nums.length;
        String[] dp = new String[len + 1];
        dp[1] = nums[0] + "";

        for (int i = 2; i <= len; i++) {

            String cur = nums[i - 1] + "";
            System.out.println(Long.valueOf(cur + dp[i - 1]) > Long.valueOf(dp[i - 1] + cur));

            dp[i] = Math.min(Long.valueOf(cur + dp[i - 1]), Long.valueOf(dp[i - 1] + cur)) + "";
        }

        return dp[len] + "";
    }

    public String minNumber2(int[] nums) {
        if (nums == null || nums.length == 0) return "";
        int len = nums.length;
        if (len == 1) return nums[0] + "";

        String[] arr = new String[len];
        for (int i = 0; i < len; i++) {
            arr[i] = nums[i] + "";
        }
        Arrays.sort(arr, (x, y) -> (x + y).compareTo(y + x));
        StringBuffer buffer = new StringBuffer();
        for (String item : arr) {
            buffer.append(item);
        }
        return buffer.toString();
    }

    //剑指61.扑克牌中的顺子
    public boolean isStraight(int[] nums) {
        if (nums == null) return false;
        int infinite = 0;
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                infinite++;
                continue;
            }
            //放入手里
            list.add(nums[i]);
        }
        Collections.sort(list);
        //检查手中的牌
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) == list.get(i - 1)) return false;
            int tem = list.get(i) - list.get(i - 1);
            if (tem > 1) {
                int need = tem - 1;
                infinite -= need;
                if (infinite < 0) return false;
            }
        }

        return true;
    }

    //剑指40.最小的k个数
    public int[] getLeastNumbers(int[] arr, int k) {
        return null;
    }


    public static void main(String[] args) {
        t20211121 t20211121 = new t20211121();
        System.out.println((double) (3 + 2) / 2);

    }
}

class Te implements Comparator<Integer> {
    int val;

    public Te(int val) {
        this.val = val;
    }

    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }

    public static void main(String[] args) {
        ArrayList<Te> list = new ArrayList<>();

        list.add(new Te(9));
        list.add(new Te(1));
        System.out.println(list.get(0).val);
        Collections.sort(list, new Comparator<Te>() {
            @Override
            public int compare(Te o1, Te o2) {
                return 0;
            }
        });
        System.out.println(list.get(0).val);
    }

}

//剑指41.数据流中的中位数
class MedianFinder {

    Queue<Integer> small, big;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        small = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        big = new PriorityQueue<>((x, y) -> y - x);// 大顶堆，保存较小的一半
    }

    public void addNum(int num) {
        if (big.size() != small.size()) {
            small.add(num);
            big.add(small.poll());
        } else {
            big.add(num);
            small.add(big.poll());
        }
    }

    public double findMedian() {
        return small.size() == big.size() ? (big.peek() + small.peek()) / 2.0 : small.peek();
    }

    public static void main(String[] args) {
        MedianFinder finder = new MedianFinder();


        PriorityQueue<Integer> queue = new PriorityQueue<>((x, y) -> x - y);
        queue.add(5);
        queue.add(2);
        System.out.println(queue.poll());

    }
}
